package com.cwj.lab3;

import com.cwj.lab1.LinkQueue;
import com.cwj.lab1.myArrayList;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Graph_table<T> {
    public static class Node<T>{
        T data;
        myArrayList<edge>list;

        public Node() {
            this.list=new myArrayList<>();
        }

        public Node(T data) {
            this.data = data;
            this.list=new myArrayList<>();
        }
    }
    public static class edge {
        int val;//权值
        int to;//尾结点数据编号

        public edge(  int ind,int val) {
            this.val = val;
            this.to = ind;
        }
    }
    private myArrayList<Node<T>>list;
    private myArrayList<Integer>inList;
    private int V_num;
    private int E_num;

    public Graph_table() {
        this.V_num=0;
        this.E_num=0;
    }

    public Graph_table(myArrayList<Node<T>> list, int v_num, int e_num) {
        this.list = list;
        V_num = v_num;
        E_num = e_num;
    }

    private void init_table(int v_num, int e_num) {
        V_num = v_num;
        E_num = e_num;
        this.list=new myArrayList<>();
        this.inList=new myArrayList<>();
        for (int i = 0; i < v_num; i++) {
            this.list.addLast(new Node<T>());
            this.inList.addLast(0);
        }
    }
    public  void initGraph(String path) throws FileNotFoundException {
        Scanner in=new Scanner(new File(path));
        int v=0,e=0;
        v=in.nextInt();e=in.nextInt();
        this.init_table(v,e);
        int start=0,end=0;
        for (int i = 0; i < e; i++) {
            this.list.get(start=in.nextInt()).list.addLast(new edge(end=in.nextInt(),in.nextInt()));
            //this.list.get(end).list.addLast(new edge(0,start));
            this.inList.set(end,inList.get(end)+1);
        }
    }
    public myArrayList<Integer> Sort(){
        myArrayList<Integer>res=new myArrayList<>();
        LinkQueue<Integer> que=new LinkQueue<>();
        for (int i = 0; i < inList.size(); i++) {
            int temp=this.inList.get(i);
            if(temp==0){
                que.push(temp);
            }
        }
        Integer top=0;
        myArrayList<edge>edgeList=null;
        while(!que.isEmpty()){
            res.addLast(top=que.pop());
            int Len=this.list.get(top).list.size();
            edgeList=this.list.get(top).list;
            for (int i = 0; i <Len ; i++) {
                int to=edgeList.get(i).to;
                this.inList.set(to,this.inList.get(to)-1);
                if(this.inList.get(to)==0){
                    que.push(to);
                }
            }
        }
        return res;
    }

    public static void main(String[] args) throws FileNotFoundException {
        String path="src/src/com/cwj/lab3/TopSort_data";
        Graph_table<Integer>graph=new Graph_table<>();
        graph.initGraph(path);
        graph.Sort().show();
    }
}
